package com.kuang.str;

/*
* 给你一个字符串 s，找到 s 中最长的 回文子串

示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"
* */


/**
 * @author kjx
 */
public class FIndMaxPaliStr {


    //第一种，暴力解法 O(n3)
    //这种方法太唐了，也没进行剪枝啥的，直接给我leetcode通过153/154,复杂度过高
    public static String longestPalindrome(String s) {
        int maxLength = 0;
        String result = null;
        //双循环暴力求解
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j <= s.length(); j++) {
                String substring = s.substring(i, j);
                int length = getPaliNum(substring);
                result = length > maxLength ? substring : result;
                maxLength = Math.max(maxLength, length);
            }
        }
        return result;
    }

    //根据输入字符串返回回文字符串的长度，非回文为0
    public static int getPaliNum(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) {
                return 0;
            }
        }
        return str.length();
    }


    //第二种从中间往两边扩散，有动态规划的影子
    public static String longestPalindrome2(String s) {
        int maxLen = 0, resLeft = 0, resRight = 0;
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            int left = i, right = i;
            //babab奇数类型
            while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
                if (right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    resLeft = left;
                    resRight = right;
                }
                left--;
                right++;
            }

            //cbbd偶数类型
            left = i;
            right = i + 1;
            while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
                if (right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    resLeft = left;
                    resRight = right;
                }
                left--;
                right++;
            }
        }

        return s.substring(resLeft, resRight + 1);
    }


    public static void main(String[] args) {
        int i = 0, j = 0, k = 0;
        i++;
        j = j + 1;
        k += 1;
    }
}
